//
// Created by 郑楚彬 on 2018/5/25.
//
/**
 * 直接查找法
 *
 * @param a
 * @param n
 * @param key
 * @return
 */
int sqSearch(int a[], int n, int key){
    for(int i=0; i<n; i++){
        if(a[i] == key)
            return i;
    }
    return -1;
}

/**
 * 折半查找 (要求线性表是有序的)
 *
 * @param R
 * @param low
 * @param high
 * @param key
 * @return
 */
int binarySearch(int R[], int low, int high, int key){
    int mid;
    while(low <= high){
        mid = (low+high)/2;
        if(R[mid] == key){
            return mid;
        }else if(R[mid] > key){
            high = mid - 1;
        }else{
            low = mid + 1;
        }
    }
    return -1;
}


/**
 * 循环有序的数组进行二分查找
 * @param A
 */
public static int find(int[] A, int n, int target){
    if(n<=0)
        return -1;
    int left = 0, right = n-1;
    while(left<=right)
    {
        int mid = left + ((right-left)/2);
        if(A[mid] == target){
            return mid;
        }
        //转折点在右半边
        if(A[left] <= A[mid])
        {
            if(A[left] <= target && target < A[mid]){
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        else //转折点在左半边
        {
            if(A[mid] < target && target <= A[right]){
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
}
